"""http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html"""
"""
字符串匹配

输入：lalopalalali lala
输出：      ^

给定一个长度为 n 的字符串 s 和一个长度为 m 的待匹配模式字符串 t，
我们希望找到 t 在 s 中第一次出现时的下标 i。
当 t 不是 s 的子串时，返回值应该是 -1。

举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？
"""


def func(s, t):
    """
    穷举/暴力匹配/朴素匹配算法
    这种算法用来测试所有 t 在 s 中可能出现的位置，
    并逐个比较字符，检查 t 是否与 s[i, …, i + m-1] 相关。
    最坏情况下的时间复杂度是 O(nm)。
    """
    assert t != ""
    n = len(s)
    m = len(t)

    for i in range(n):
        if s[i:i + m] == t:
            return i
    else:
        return -1


"""
我们把两个字符串 x 和 y 的重叠部分称为最长单词，
这个最长单词既是 y 的严格后缀，又是 x 的严格前缀。

在发现 s[i] 和 t[j] 有差异的时候，我们把 t 向 s 的尾部移动（从 0 到 i-1），以便进行后续比较。

由于 s[0, …, 1] 的前缀是 t[0,…, j-1]（最后 j 次比较已经证明了 s[i-j,…, i-1] 和 t[0,…, j-1] 相等），因此 t 向后移动的距离仅由 t 来决定。
我们可以通过预先计算来确定 t 向后偏移的距离。
用 r[j] 来记录 j 减去自身与 t[0, …, j-1] 的重叠部分的差值。

下面的程序展示了具体实现方式。
为了分析复杂度，我们把计算 r 的代码和字符串匹配的代码分开：第一部分代码的复杂度是 O(m)，第二部分代码的复杂度是 O(n)。
每当 s[i] = t[j] 时，都需要把 j 增加 1；而每次两者不相等的时候，要把 j 减少 1，因为 r[j] ＜ j。
既然 s[i] 和 t[j] 最多只有 n 次相等，而且 j 永远是非负值，那么两者不相等的次数最多也只有 n。
"""
"""
第一步预处理计算了带匹配的模式字符串 t 的每个子字符串的最大前缀和后缀的公共元素长度，
即 t 本身包含的重复字符和字符组合。

这样一来，每次匹配失败时，带匹配字符串不是通过简单地向后移动一位来继续查找，
而是根据预先算好的前缀和后缀的公共元素表来跳过一定数量的字符，
以此直接匹配 t 中重复的字符串或字母组合，从而提高效率。

比如，字符串 s 是 DEABCABABCADE，字符串 t 是 ABCAD。
t 中两个 A 重复出现，第一次 ABCAD 匹配 ABCAB 在最后一个字符 D 和 B 比较时失败，

此时，我们准确地知道匹配失败的字符 D 的前一个字符 A 匹配成功了，
即 ABCA 都匹配成功了，那么我们就不再需要比较 s 中的其他字母。

也就是说，不是将 t 中的 A 和 s 中的 B 比较，
而是直接用已经匹配成功的 t 中的 A 来和 s 中的 A 对齐。
再次强调，由于 t 中有两个 A 重复，而其他字符都不是 A，
那么我们希望匹配 s 中的 A 时，只能用 t 中的两个 A 中的一个来对齐 s 中的 A，
这样就跳过了一定不相等的 B 和 C 等字符。
"""


def knuth_morris_pratt(s, t):
    """
    Knuth-Morris-Pratt算法

    :param s: str, 字符串数组
    :param t: str, 字符串数组
    :return: int, 返回两个字符串数组中相邻元素的索引下标
    """
    # 检查字符串是否为空
    assert t != ""
    # 计算字符串数组的长度
    n = len(s)
    # 初始化变量 r 为 0 并指向字符串数组的第一个元素
    m = len(t)
    # 分配内存并初始化变量 j
    r = [0] * m
    j = r[0] = -1
    # 循环遍历字符串数组 s 和 t
    for i in range(1, m):
        # 循环遍历相邻元素
        while j >= 0 and t[i - 1] != t[j]:
            j = r[j]
        # 更新 j 并循环遍历相邻元素
        j += 1
        r[i] = j
    # 循环遍历字符串数组 s 和 t
    for i in range(n):
        # 循环遍历相邻元素
        while j >= 0 and s[i] != t[j]:
            j = r[j]
        # 更新 j 并循环遍历相邻元素
        j += 1
        if j == m:
            # 如果 j 等于 m，则返回相邻元素之间的差值
            return i - m + 1
        # 如果 j 不等于 m，则返回 -1
        if j >= m:
            return -1
    # 如果循环遍历完所有相邻元素仍然返回 -1，则算法失败
    return -1


def test():
    # print(func('lalopalalali', 'lala'))
    print(knuth_morris_pratt('lalopalalali', 'lala'))


if __name__ == '__main__':
    test()
